package com.study.chunguard.common.utils.tree;

import cn.hutool.core.lang.Filter;
import cn.hutool.core.util.ObjectUtil;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

/**
 * 树工具类
 *
 * @author zhaowenhao
 * @since 2023-05-09
 */
public class TreeUtil {

    private TreeUtil() {
        throw new IllegalStateException("Utility class");
    }

    /**
     * 构建树
     * <p>
     * 根据指定的根结点id和节点列表（不带子节点）构造一棵树，
     * 如果节点列表中不包含id为rootId的元素，
     * 就使用TreeNode接口createEmpty()创建一个空树节点，
     * 设置空树节点的id为rootId,用来作为根节点
     * 然后逐级增加子节点，返回根节点的子节点列表
     *
     * @param treeNodes 树节点列表
     * @param rootId    最顶层父id值 一般为 0 之类
     * @param <T>       ID类型
     * @param <N>       节点类型
     * @return {@link List}  树节点列表
     */
    public static <T, N extends TreeNode<T, N>> List<N> build(List<N> treeNodes, T rootId) {
        return build(treeNodes, rootId, Boolean.FALSE);
    }

    /**
     * 构建树
     * <p>
     * 根据指定的根结点id和节点列表（不带子节点）构造一棵树，
     * 如果节点列表中不包含id为rootId的元素，
     * 就使用TreeNode接口createEmpty()创建一个空树节点，
     * 设置空树节点的id为rootId,用来作为根节点
     * 然后逐级增加子节点，返回根节点的子节点列表
     *
     * @param treeNodes                  树节点列表
     * @param rootId                     最顶层父id值 一般为 0 之类
     * @param shouldGenerateParentDetail 是否生成父节点详情，父节点详情只包含父节点普通的字段，不包含父节点、子节点等信息，防止循环引用，
     *                                   由于生成父节点详情需要执行节点复制操作，非常影响性能，所以默认不生成
     * @param <T>                        ID类型
     * @param <N>                        节点类型
     * @return {@link List}  树节点列表
     */
    public static <T, N extends TreeNode<T, N>> List<N> build(List<N> treeNodes, T rootId, boolean shouldGenerateParentDetail) {
        return buildSingle(treeNodes, rootId, shouldGenerateParentDetail).getChildren();
    }

    /**
     * 构建单root节点树
     * <p>
     * 根据指定的根结点id和节点列表（不带子节点）构造一棵树，
     * 如果节点列表中不包含id为rootId的元素，
     * 就使用TreeNode接口createEmpty()创建一个空树节点，
     * 设置空树节点的id为rootId,用来作为根节点
     * 然后逐级增加子节点，返回根节点
     *
     * @param <T>       ID类型
     * @param <N>       节点类型
     * @param treeNodes 树节点列表
     * @param rootId    最顶层父id值 一般为 0 之类
     * @return {@link TreeNode}  根节点
     */
    public static <T, N extends TreeNode<T, N>> N buildSingle(List<N> treeNodes, T rootId) {
        return buildSingle(treeNodes, rootId, Boolean.FALSE);
    }

    /**
     * 构建单root节点树
     * <p>
     * 根据指定的根结点id和节点列表（不带子节点）构造一棵树，
     * 如果节点列表中不包含id为rootId的元素，
     * 就使用TreeNode接口createEmpty()创建一个空树节点，
     * 设置空树节点的id为rootId,用来作为根节点
     * 然后逐级增加子节点，返回根节点
     *
     * @param <T>                        ID类型
     * @param <N>                        节点类型
     * @param treeNodes                  树节点列表
     * @param rootId                     最顶层父id值 一般为 0 之类
     * @param shouldGenerateParentDetail 是否生成父节点详情，父节点详情只包含父节点普通的字段，不包含父节点、子节点等信息，防止循环引用，
     *                                   由于生成父节点详情需要执行节点复制操作，非常影响性能，所以默认不生成
     * @return {@link TreeNode}  根节点
     */
    public static <T, N extends TreeNode<T, N>> N buildSingle(List<N> treeNodes, T rootId, boolean shouldGenerateParentDetail) {
        return new TreeBuilder<>(treeNodes, rootId, shouldGenerateParentDetail).append(treeNodes).build();
    }

    /**
     * 构建树
     * <p>
     * 根据指定的根结点id和id-节点（不带子节点）Map构造一棵树，
     * 如果节点Map的key中不包含rootId，
     * 就使用TreeNode接口createEmpty()创建一个空树节点，
     * 设置空树节点的id为rootId,用来作为根节点
     * 然后逐级增加子节点，返回根节点的子节点列表
     *
     * @param treeMap 树节点Map
     * @param rootId  最顶层父id值 一般为 0 之类
     * @param <T>     ID类型
     * @param <N>     节点类型
     * @return {@link List}  树节点列表
     */
    public static <T, N extends TreeNode<T, N>> List<N> build(Map<T, N> treeMap, T rootId) {
        return build(treeMap, rootId, Boolean.FALSE);
    }

    /**
     * 构建树
     * <p>
     * 根据指定的根结点id和id-节点（不带子节点）Map构造一棵树，
     * 如果节点Map的key中不包含rootId，
     * 就使用TreeNode接口createEmpty()创建一个空树节点，
     * 设置空树节点的id为rootId,用来作为根节点
     * 然后逐级增加子节点，返回根节点的子节点列表
     *
     * @param treeMap                    树节点Map
     * @param rootId                     最顶层父id值 一般为 0 之类
     * @param shouldGenerateParentDetail 是否生成父节点详情，父节点详情只包含父节点普通的字段，不包含父节点、子节点等信息，防止循环引用，
     *                                   由于生成父节点详情需要执行节点复制操作，非常影响性能，所以默认不生成
     * @param <T>                        ID类型
     * @param <N>                        节点类型
     * @return {@link List}  树节点列表
     */
    public static <T, N extends TreeNode<T, N>> List<N> build(Map<T, N> treeMap, T rootId, boolean shouldGenerateParentDetail) {
        return buildSingle(treeMap, rootId, shouldGenerateParentDetail).getChildren();
    }

    /**
     * 构建单root节点树
     * <p>
     * 根据指定的根结点id和id-节点（不带子节点）Map构造一棵树，
     * 如果节点Map的key中不包含rootId，
     * 就使用TreeNode接口createEmpty()创建一个空树节点，
     * 设置空树节点的id为rootId,用来作为根节点
     * 然后逐级增加子节点，返回根节点
     *
     * @param treeMap 树节点Map
     * @param rootId  最顶层父id值 一般为 0 之类
     * @param <T>     ID类型
     * @param <N>     节点类型
     * @return {@link TreeNode}  根节点
     */
    public static <T, N extends TreeNode<T, N>> N buildSingle(Map<T, N> treeMap, T rootId) {
        return buildSingle(treeMap, rootId, Boolean.FALSE);
    }

    /**
     * 构建单root节点树
     * <p>
     * 根据指定的根结点id和id-节点（不带子节点）Map构造一棵树，
     * 如果节点Map的key中不包含rootId，
     * 就使用TreeNode接口createEmpty()创建一个空树节点，
     * 设置空树节点的id为rootId,用来作为根节点
     * 然后逐级增加子节点，返回根节点
     *
     * @param treeMap                    树节点Map
     * @param rootId                     最顶层父id值 一般为 0 之类
     * @param shouldGenerateParentDetail 是否生成父节点详情，父节点详情只包含父节点普通的字段，不包含父节点、子节点等信息，防止循环引用，
     *                                   由于生成父节点详情需要执行节点复制操作，非常影响性能，所以默认不生成
     * @param <T>                        ID类型
     * @param <N>                        节点类型
     * @return {@link TreeNode}  根节点
     */
    public static <T, N extends TreeNode<T, N>> N buildSingle(Map<T, N> treeMap, T rootId, boolean shouldGenerateParentDetail) {
        return new TreeBuilder<>(treeMap, rootId, shouldGenerateParentDetail).append(treeMap).build();
    }

    /**
     * 递归遍历树，根据过滤器筛选节点,并返回新的树
     *
     * @param treeNode 树节点
     * @param filter   过滤器
     * @param <T>      ID类型
     * @param <N>      节点类型
     * @return {@link List}  过滤后的树节点列表
     */
    public static <T, N extends TreeNode<T, N>> N filterNew(N treeNode, Filter<N> filter) {
        if (treeNode == null) {
            return null;
        }
        return treeNode.cloneTree().filter(filter);
    }

    /**
     * 递归遍历树，根据过滤器筛选节点
     *
     * @param treeNode 树节点
     * @param filter   过滤器
     * @param <T>      ID类型
     * @param <N>      节点类型
     * @return {@link List} 过滤后的树节点列表
     */
    public static <T, N extends TreeNode<T, N>> N filter(N treeNode, Filter<N> filter) {
        if (treeNode == null) {
            return null;
        }
        return treeNode.filter(filter);
    }


    /**
     * 获取ID对应的节点，如果有多个ID相同的节点，只返回第一个。<br>
     * 此方法只查找此节点及子节点，采用递归深度优先遍历。
     *
     * @param <T>  ID类型
     * @param <N>  节点类型
     * @param node 节点
     * @param id   ID
     * @return 节点
     */
    public static <T, N extends TreeNode<T, N>> N getNode(N node, T id) {
        if (ObjectUtil.equal(id, node.getId())) {
            return node;
        }

        final List<N> children = node.getChildren();
        if (null == children) {
            return null;
        }

        // 查找子节点
        N childNode;
        for (N child : children) {
            childNode = getNode(child, id);
            if (null != childNode) {
                return childNode;
            }
        }

        // 未找到节点
        return null;
    }

    /**
     * 获取所有父节点名称列表
     *
     * <p>
     * 比如有个人在研发1部，他上面有研发部，接着上面有技术中心<br>
     * 返回结果就是：[研发一部, 研发中心, 技术中心]
     *
     * @param <T>                节点ID类型
     * @param node               节点
     * @param includeCurrentNode 是否包含当前节点的名称
     * @return 所有父节点名称列表，node为null返回空List
     */
    public static <T, N extends TreeNode<T, N>> List<CharSequence> getParentNames(N node, boolean includeCurrentNode) {
        final List<CharSequence> result = new ArrayList<>();
        if (null == node) {
            return result;
        }

        if (includeCurrentNode) {
            result.add(node.getName());
        }

        N parent = node.getParent();
        while (null != parent) {
            result.add(parent.getName());
            parent = parent.getParent();
        }
        return result;
    }

    /**
     * 获取所有父节点ID列表
     * <p>
     * <p
     *
     * @param <T>                节点ID类型
     * @param node               节点
     * @param includeCurrentNode 是否包含当前节点的名称
     * @return 所有父节点ID列表，node为null返回空List
     */
    public static <T, N extends TreeNode<T, N>> List<T> getParentIds(N node, boolean includeCurrentNode) {
        final List<T> result = new ArrayList<>();
        if (null == node) {
            return result;
        }

        if (includeCurrentNode) {
            result.add(node.getId());
        }

        N parent = node.getParent();
        while (null != parent) {
            result.add(parent.getId());
            parent = parent.getParent();
        }
        return result;
    }

}
